# 接雨水：
class Solution:
    def trap(self, height: list) -> int:
        """
            暴力破解， 求每根柱子上能盛下多少水
            需要找到柱子左边第一个大于自己的柱子，和右边第一个大于自己的柱子。盛水 = min(左， 右) - 当前柱子高度
        """
        n = len(height)
        ans = 0
        for i in range(n):
            # 当前柱子高度
            high = height[i]
            # 左边柱子， 右边柱子
            left = right = 0
            for j in range(n):
                if j < i: left = max(height[j], left)
                if j > i: right = max(height[j], right)
            # 计算当前柱子的积水
            ans += max(min(left, right) - high, 0) 
            # print(i, left, right, high, max(min(left, right) - high, 0) )

        return ans

# 暴力破解优化
class Solution:
    def trap(self, height: list) -> int:
        """
            暴力破解优化
            空间换取时间， 可以看到， 每根柱子都需要 遍历一遍数组才知道自己左边，右边最大的是谁
            可以提前求出来所有数的左边右边，这样就优化了一些, 两次遍历求左右最大值，一次遍历求结果
            时间复杂度： O(3n)
            空间复杂度： O(2n) , 多使用两个数组
        """
        n, ans = len(height), 0

        # 计算左右两边最大的
        leftMax = [0] * n
        for i in range(1, n):
            leftMax[i] = max(leftMax[i-1], height[i-1])

        rightMax = [0] * n
        for i in range(n-2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i + 1])
        
        # 计算每个柱子的盛水
        for i in range(n):
            # 当前柱子高度
            high = height[i]
            # 计算当前柱子的积水
            ans += max(min(leftMax[i], rightMax[i]) - high, 0) 

        return ans


# 接雨水：
class Solution:
    def trap(self, height: list) -> int:
        """
            设想一下，要能接水，至少需要三根柱子，并且前两根是单调递减的， 第三根柱子高起来才能接到水。那么可以使用单调栈实现。
            保持栈内一直存储单调递减的柱子，碰到高柱子，依次计算乘水量，柱子一样高时，不能入栈，但是下次碰到高柱子时，要记得宽是两个单位，
            所以压入栈的 是元素的下标
        """
        n = len(height)
        stack = list()
        rst = 0
        for i in range(n):
            if not stack or height[stack[-1]] > height[i]:    
                stack.append(i)
            else:
                while stack and height[stack[-1]] < height[i]:
                    # 弹出当前栈顶柱子，并计算柱子高
                    curHigh = height[stack.pop()]
                    # 判断前面还有柱子，没柱子就把当前柱子放进去当成第一根柱子
                    if not stack: break
                    # 计算盛水面积的高
                    high = min(height[stack[-1]], height[i]) 
                    # 计算盛水面积的宽
                    width = i - stack[-1] - 1
                    print(high, width)
                    # 计算盛水面积
                    rst += (high - curHigh) * width

                stack.append(i)    

        return rst

# 优化上面的代码，仔细一想，其实就是求右边第一个大于自己的。然后再计算接到的雨水
class Solution:
    def trap(self, height: list) -> int:
        """
            设想一下，要能接水，至少需要三根柱子，并且前两根是单调递减的， 第三根柱子高起来才能接到水。那么可以使用单调栈实现。
            保持栈内一直存储单调递减的柱子，碰到高柱子，依次计算乘水量，柱子一样高时，不能入栈，但是下次碰到高柱子时，要记得宽是两个单位，
            所以压入栈的 是元素的下标
        """
        n = len(height)
        stack = list()
        rst = 0
        for i in range(n):
            while stack and height[stack[-1]] < height[i]:
                # 弹出当前栈顶柱子，并计算柱子高
                curHigh = height[stack.pop()]
                # 判断前面还有柱子，没柱子就把当前柱子放进去当成第一根柱子
                if not stack: break
                # 计算盛水面积的高
                high = min(height[stack[-1]], height[i]) 
                # 计算盛水面积的宽
                width = i - stack[-1] - 1
                print(high, width)
                # 计算盛水面积
                rst += (high - curHigh) * width

            stack.append(i)    

        return rst


# 双指针最优解
class Solution:
    def trap(self, height: list) -> int:
        ans = 0
        left, right = 0, len(height) - 1
        leftMax = rightMax = 0

        while left < right:
            leftMax = max(leftMax, height[left])
            rightMax = max(rightMax, height[right])
            if height[left] < height[right]:
                ans += leftMax - height[left]
                left += 1
            else:
                ans += rightMax - height[right]
                right -= 1
        
        return ans


height = [0,1,0,2,1,0,1,3,2,1,2,1]

s = Solution()
rst = s.trap(height)
print(rst)